
#include "process.h"
#include "pqueue.h"
#include <stdio.h>
#include <stdlib.h>


static int insert_rec(struct pqueue*, int); 
static int restore_heap(struct pqueue*, int);
static void swap(struct pqueue*, int, int);

/* By Cliff Buchanan and Jacob Eichers. Contains the functions and 
	functionality to implement the priority queue which assists the stcp 
	scheduler.*/

/* create a heap*/
struct pqueue *pq_create()
{
	struct pqueue *priority;
	priority = malloc(sizeof(struct pqueue));

	priority->loc = 0;

	return priority;
}

/* add a process to the pqueue.
	returns -1 if the heap is full, but returns 0 if successful*/
int pq_insert(struct pqueue *priority, struct process *proc)
{
	if (priority->loc < HEAPSIZE)
	{

		priority->loc++;
		priority->heap[priority->loc] = proc;
		insert_rec(priority, priority->loc);
		
		return 0;
	}
	else
		{return -1;}
}

/* helper method for pq_insert. Recursivly balances heap after adding.*/
static int insert_rec(struct pqueue *priority, int index)
{
	int childTime, parentTime;
	/* if we return -1 it means we've reached the root*/
	if (index == HEAPROOT)
		{return -1;}
	/* check to see if the child is greater than the parent */
	childTime = priority->heap[index]->lifeTime 
		- priority->heap[index]->time;
	parentTime = priority->heap[index/2]->lifeTime 
		- priority->heap[index/2]->time;
	
	if (childTime < parentTime)
	{
		/* swap the values if the value inserted is smaller*/
		swap(priority, index/2, index);
		insert_rec(priority, index/2);
	}
	/*else it will return 0, meaning it has successfully been sorted*/
	return 0;
		
}

/* look at the minimum, but don't take it off*/
struct process *pq_peek(struct pqueue *priority)
{
	/* check to make sure we don't cause a segfault*/
	if (priority->loc > 0)
		{return priority->heap[HEAPROOT];}
	return NULL;
}

/* remove element from pqueue. Returns null if empty */
struct process *pq_remove(struct pqueue *priority)
{
	if (priority->loc > 0)
	{
		/*store the root so we can return it at the end of the function*/
		struct process *shortestJob = priority->heap[HEAPROOT];
		/* make the lowest child the new root*/
		priority->heap[HEAPROOT] = priority->heap[priority->loc];
		/*decrease the size of the heap*/
		priority->loc--;
		/* restore the heap characteristics of the data structure*/
		restore_heap(priority, HEAPROOT);
	
		return shortestJob;
	}
	return NULL;
}

/* helper method for pq_remove. Recursivly restores heap.*/
static int restore_heap (struct pqueue *priority, int index)
{
	int time, right, rightTime, left, leftTime;
	if (2*index <= priority->loc)
	{
		time = priority->heap[index]->lifeTime 
			- priority->heap[index]->time;
		left = 2*index;
		leftTime = priority->heap[left]->lifeTime 
			- priority->heap[left]->time;

		/* if there is no right node */
		if ((2*index + 1) > priority->loc)
		{
			if (time > leftTime)
			{
 			/* swap the left node with the parent node*/

 				swap(priority, index, left);
			}
			/* if we don't have a right node, we can assume we are at the
				bottom of the heap */
			return 0;
		}
		
		right = 2*index + 1;
		rightTime = priority->heap[right]->lifeTime 
			- priority->heap[right]->time;	
		
 		if (time < leftTime && time < rightTime)
 		{
 			return 1;
 		}
		else if( leftTime <= rightTime)
 		{
 			/* swap the left node with the parent node*/
 			swap(priority, left, index);
			restore_heap(priority, left);
			
 		}
		else if (rightTime < leftTime)
 		{
 			/* swap the right node with the parent node*/
 			swap(priority, right, index);
 			restore_heap(priority, right);
 			
 		}
 	}
 	return 0;
}

/* returns 0 iff pqueue is not empty*/
int pq_is_empty(struct pqueue *priority)
{
	/* if the heap is empty, the location will be at 0*/
	if (priority->loc == 0)
		{return 1;}
	/* there should be no situation in which loc < 0 return an error value*/
	if (priority->loc < 0)
		{return -1;}
	/* otherwise, it has values in it, so it is not empty*/
	return 0;
}

/* helper method to swap elements by index*/
static void swap(struct pqueue *priority, int index1, int index2)
{
	struct process *temp = priority->heap[index1];
 	priority->heap[index1] = priority->heap[index2];
 	priority->heap[index2] = temp;
}
